摘要 :
Assume that n is a positive integer with n ≥ 2. It is proved that between any two different vertices x and y of Q_n there exists a path P_l(x,y) of length l for any l with h(x,y) ≤ l ≤ 2~n - 1 and 2|(l - h(x,y)). We expect such...
展开
Assume that n is a positive integer with n ≥ 2. It is proved that between any two different vertices x and y of Q_n there exists a path P_l(x,y) of length l for any l with h(x,y) ≤ l ≤ 2~n - 1 and 2|(l - h(x,y)). We expect such path P_l(x,y) can be further extended by including the vertices not in P_l(x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Q_n, for any vertex y ∈ V(Q_n) - {x, z}, and for any integer l with h(x, y) ≤ l ≤ 2~n - 1 - h(y, z) and 2|(l - h(x, y)), there exists a hamiltonian path R(x, y, z; l) from x to z such that d_(R(x,y,z;l))(x, y) = l. Moreover, for any two distinct vertices x and y of Q_n and for any integer l with h(x, y) ≤ l ≤ 2~(n-1) and 2|(l - h(x, y)), there exists a hamiltonian cycle S(x, y;l) such that d_(S(x,y;l))(x, y) = l.
收起
摘要 :
Due to advances in fiber optics and VLSI technology, interconnection networks that allow simultaneous broadcasts are becoming feasible. Distributed shared memory (DSM) implementations on such networks promise high performance even...
展开
Due to advances in fiber optics and VLSI technology, interconnection networks that allow simultaneous broadcasts are becoming feasible. Distributed shared memory (DSM) implementations on such networks promise high performance even for small applications with small granularity. This paper, after summarizing the architecture of one such implementation called the Simultaneous Multiprocessor Optical Exchange Bus (SOME-Bus), presents simple algorithms for improving the performance of parallel programs running on the SOME-Bus multiprocessor implementing cache-coherent DSM. The algorithms are based on run-time data redistribution via dynamic page migration protocol. They use memory access references together with the information of average channel utilization, average channel waiting time, number of messages in the channel queue or short-term average channel waiting time reported by each node and gathered by hardware monitors to make correct decisions related to the placement of shared data. Simulations with four parallel codes on a 64-processor SOME-Bus show that the algorithms yield significant performance improvements such as reduction in the execution times, number of remote memory accesses, average channel waiting times, average network latencies and increase in average channel utilizations. (C) 2007 Elsevier B.V. All rights reserved.
收起
摘要 :
Interconnection networks provide communication among processors, memory modules, and other devices in parallel computer systems. The number of stages, interconnection topology, and the types of SE used in the network configuration...
展开
Interconnection networks provide communication among processors, memory modules, and other devices in parallel computer systems. The number of stages, interconnection topology, and the types of SE used in the network configuration differentiate each interconnection network. As an illustration, there are numerous aspects that are important in the development of interconnection networks. Reliability can be considered as an important factor to measure the performance in the network. The reliability for interconnection network depends on the reliability of its components. In this paper, we examine the various topologies of interconnection, communication protocol, and discuss reliability issues related to interconnection network.
收起
摘要 :
Multistage Interconnection Networks (MINs) are an effective means of communication between multiple processors and memory modules in many parallel processing systems. Literature consists of numerous fault-tolerant MIN designs. How...
展开
Multistage Interconnection Networks (MINs) are an effective means of communication between multiple processors and memory modules in many parallel processing systems. Literature consists of numerous fault-tolerant MIN designs. However, due to the recent advances in the field of parallel processing, requiring large processing power, an increase in the demand to design and develop more reliable, cost-effective and fault-tolerant MINs is being observed. This work proposes two novel MIN designs, namely, Augmented-Shuffle Exchange Gamma Interconnection Network (A-SEGIN) and Enhanced A-SEGIN (EA-SEGIN). The proposed MINs utilize chaining of switches, and multiplexers & demultiplexers for providing a large number of alternative paths and thereby better fault tolerance. Different reliability measures, namely, 2-terminal, multi-source multi-destination, broadcast and network/global, respectively, of the proposed MINs have been evaluated with the help of all enumerated paths and well-known Sum-of-Disjoint Products approach. Further, overall performance, with respect to the number of paths, different reliability measures, hardware cost and cost per unit, of the proposed MINs has been compared with 19 other well-studied MIN layouts. The results suggest that the proposed MINs are very strong competitors of the preexisting MINs of their class owing to their better reliability and cost effectiveness.
收起
摘要 :
Tens and eventually hundreds of processing cores are projected to be integrated onto future microprocessors, making the global interconnect a key component to achieving scalable chip performance within a given power envelope. Whil...
展开
Tens and eventually hundreds of processing cores are projected to be integrated onto future microprocessors, making the global interconnect a key component to achieving scalable chip performance within a given power envelope. While CMOS-compatible nanophotonics has emerged as a leading candidate for replacing global wires beyond the 22nm timeframe, on-chip optical interconnect architectures proposed thus far are either limited in scalability or are dependent on comparatively slow electrical control networks. In this paper, we present Phastlane, a hybrid electrical/optical routing network for future large scale, cache coherent multicore microprocessors. The heart of the Phastlane network is a low-latency optical crossbar that uses simple predecoded source routing to transmit cache-line-sized packets several hops in a single clock cycle under contentionless conditions. When contention exists, the router makes use of electrical buffers and, if necessary, a high speed drop signaling network. Overall, Phastlane achieves 2X better network performance than a state-of-the-art electrical baseline while consuming 80% less network power.
收起
摘要 :
We generalise the biswapped network Bsw(G) to obtain a multiswapped network Msw(H; G), built around two graphs C and H. We show that the network Msw(H; G) lends itself to optoelectronic implementation and examine its topological a...
展开
We generalise the biswapped network Bsw(G) to obtain a multiswapped network Msw(H; G), built around two graphs C and H. We show that the network Msw(H; G) lends itself to optoelectronic implementation and examine its topological and algorithmic. We derive the length of a shortest path joining any two vertices in Msw(H; C) and consequently a formula for the diameter. We show that if C has connectivity k≥1 and H has connectivity λ≥1 where λ≤k then Msw(H; C) has connectivity at least k + X, and we derive upper bounds on the (k + λ)-diameter of Msw(H; C). Our analysis yields distributed routing algorithms for a distributed-memory multiprocessor whose underlying topology is Msw(H; G). We also prove that if G and H are Cayley graphs then Msw(H; C) need not be a Cayley graph, but when H is a bipartite Cayley graph then Msw(H; C) is necessarily a Cayley graph.
收起
摘要 :
Connectivity type measures form an important topic in graph theory. Such measures provide an important part of analyzing the vulnerability and resilience of interconnection networks. In this short commentary, we outline our perspe...
展开
Connectivity type measures form an important topic in graph theory. Such measures provide an important part of analyzing the vulnerability and resilience of interconnection networks. In this short commentary, we outline our perspective on the development of this topic with respect to interconnection networks.
收起
摘要 :
In Hopfield neural network with any symmetry couplings the output states converge on the minimum. However, the output state of the neural network in which the symmetry couplings are replaced by asymmetry couplings, does not conver...
展开
In Hopfield neural network with any symmetry couplings the output states converge on the minimum. However, the output state of the neural network in which the symmetry couplings are replaced by asymmetry couplings, does not converge always for the asymmetry coupling weights. A neural network with asymmetry couplings in which the output state converges, is proposed in this paper. It is possible to construct sixteen neural networks including symmetry and anti-symmetry ones, taking the assumption that the coupling functions of a unit, V{sub}i and (2- V{sub}i) can be used in energy function and dynamic equation. Each pair of the coupling weights of asymmetry neural network between two units divides into two pairs of symmetry weights and anti-symmetry weights, and two kinds of the neural network are constructed for each pair of the coupling weights. Then they are combined and connected to form the asymmetry neural network. The convergence of the network is shown and the dynamics is examined introducing extended refractoriness. The asymmetry neural network is applied to Ranking Problem in League Tournament.
收起
摘要 :
Many complex systems can be represented as networks consisting of distinct types of interactions, which can be categorized as links belonging to different layers. For example, a good description of the full protein-protein interac...
展开
Many complex systems can be represented as networks consisting of distinct types of interactions, which can be categorized as links belonging to different layers. For example, a good description of the full protein-protein interactome requires, for some organisms, up to seven distinct network layers, accounting for different genetic and physical interactions, each containing thousands of protein-protein relationships. A fundamental open question is then how many layers are indeed necessary to accurately represent the structure of a multilayered complex system. Here we introduce a method based on quantum theory to reduce the number of layers to a minimum while maximizing the distinguishability between the multilayer network and the corresponding aggregated graph. We validate our approach on synthetic benchmarks and we show that the number of informative layers in some real multilayer networks of protein-genetic interactions, social, economical and transportation systems can be reduced by up to 75%.
收起
摘要 :
Scaling trends of logic, memories, and interconnect networks lead towards dense many-core chips. Unfortunately, process yields and reticle sizes limit the scalability of large single-chip systems. Multi-chip systems break free of ...
展开
Scaling trends of logic, memories, and interconnect networks lead towards dense many-core chips. Unfortunately, process yields and reticle sizes limit the scalability of large single-chip systems. Multi-chip systems break free of these areal limits, but in turn require enormous chip-to-chip bandwidth. The "macrochip" concept presented here integrates multiple many-core processor chips in a single package with silicon-photonic interconnects. This design enables a multi-chip system to approach the performance of a single large die.
In this paper we propose three silicon-photonic network designs that provide low-power, high-bandwidth inter-die communication: a static wavelength-routed point-to-point network, a "two-phase" arbitrated network, and a limited-connectivity point-to-point network. We also adapt two existing intra-chip silicon-photonic interconnects: a token-ring-based crossbar and a circuit-switched torus.
We simulate a 64-die, 512-core cache-coherent macrochip using all of the above networks with synthetic kernels, and kernels from Splash-2 and PARSEC. We evaluate the networks on performance, optical power and complexity. Despite a narrow data-path width compared to the token-ring or torus, the point-to-point performs 3.3 × and 3.9× better respectively. We show that the point-to-point is over 10 × more power-efficient than the other networks. We also show that, contrary to electronic network designs, a point-to-point network has the lowest design complexity for an inter-chip silicon-photonic network.
收起
原文获取